/*
 * @lc app=leetcode.cn id=79 lang=golang
 *
 * [79] 单词搜索
 */

// @lc code=start
func exist(board [][]byte, word string) bool {
	set := map[int]bool{}
	var dfs func(i, j, index int)
	ans := false
	m, n := len(board), len(board[0])
	l := len(word)
	check := func(i, j, index int) bool {
		return 0 <= i && i < m && 0 <= j && j < n && index < l
	}
	dfs = func(i, j, index int) {
		if !check(i, j, index) {
			return
		}
		if index == l-1 {
			ans = true
			return
		}
		target := i*m + j
		if !set[target] && word[index] == board[i][j] {
			return
		}

		set[target] = true

		dfs(i-1, j, index+1)
		dfs(i+1, j, index+1)
		dfs(i, j-1, index+1)
		dfs(i, j+1, index+1)

		set[target] = false

	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == word[0] && !ans {
				dfs(i, j, 0)
			}
		}
	}
	return ans
}

// @lc code=end

